package com.lsa.letcode.the98.validateBst;

import com.lsa.letcode.common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;


/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode
 * left; TreeNode right; TreeNode(int x) { val = x; } }
 */
public class Solution {
	public boolean isValidBST(TreeNode r) {
		class StackFrame{
    		int step; // 0 - left, 1 - right, 2 - check
    		TreeNode root;
			StackFrame(TreeNode root) {
				this.root = root;
			}
    	}
		
		Deque<StackFrame> stack = new ArrayDeque<StackFrame>();
    	stack.add(new StackFrame(r));
    	while(!stack.isEmpty()) {
    		StackFrame f = stack.peek();
    		if (f.root == null){
    			stack.pop();
    		}
    		else {
    			int step = f.step++;
    			switch (step) {
    			case 0:
    				stack.push(new StackFrame(f.root.left));
    				break;
    			case 1:
    				stack.push(new StackFrame(f.root.right));
    				break;
    			case 2:
    				boolean isOK = isLessThan(valueOf(max(f.root.left)), f.root.val) && 
    				isLessThan(f.root.val, valueOf(min(f.root.right)));
    				if (!isOK){
    					return false;
    				}
    				else {
    					stack.pop();
    				}
    				break;
    			}
    		}
    	}
		
		return true;
	}
	public boolean isValidBSTRec(TreeNode r) {
		if (r == null) {
			return true;
		}

		if (!isValidBSTRec(r.left)) {
			return false;
		}
		
		if (!isValidBSTRec(r.right)) {
			return false;
		}

		return isLessThan(valueOf(max(r.left)), r.val) && 
				isLessThan(r.val, valueOf(min(r.right)));
	}
	
	private static TreeNode max(TreeNode r) {
		TreeNode max = null;
		while(r != null){
			max = r;
			r = r.right;
		}
		return max;
	}
	
	private static TreeNode min(TreeNode r) {
		TreeNode min = null;
		while(r != null){
			min = r;
			r = r.left;
		}
		return min;
	}

	private static Integer valueOf(TreeNode n) {
		return n == null ? null : n.val;
	}
	
	private static boolean isLessThan(Integer n1, Integer n2) {
		if (n1 == null || n2 == null){
			return true; // to satisfy BST invariant
		}
		return n1 < n2;
	}
}